//给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链
//表节点，返回 反转后的链表 。
//
// 
//
// 示例 1： 
// 
// 
//输入：head = [1,2,3,4,5], left = 2, right = 4
//输出：[1,4,3,2,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [5], left = 1, right = 1
//输出：[5]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数目为 n 
// 1 <= n <= 500 
// -500 <= Node.val <= 500 
// 1 <= left <= right <= n 
// 
//
// 
//
// 进阶： 你可以使用一趟扫描完成反转吗？ 
//
// Related Topics 链表 👍 1752 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2024-03-25 17:27:25
 * @description 92.反转链表 II
 */
public class ReverseLinkedListIi{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new ReverseLinkedListIi().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

//  Definition for singly-linked list.
  public class ListNode {
      int val;
     ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    //递归，先遍历到l，然后反转l到r，
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || left >= right) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;

        // 移动 pre 指针到 left 前一个节点
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        // 定位到需要反转的起始节点和结束节点
        ListNode start = pre.next;
        ListNode end = start;
        for (int i = 0; i < right - left; i++) {
            end = end.next;
        }

        // 截取需要反转的链表部分，并反转
        ListNode next = end.next;
        end.next = null; // 断开链表
        pre.next = reverse(start);
        start.next = next; // 重新连接链表

        return dummy.next;
    }

    // 反转链表
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    public ListNode reverseBetween1(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0, head), p0 = dummy;
        for (int i = 0; i < left - 1; ++i)
            p0 = p0.next;

        ListNode pre = null, cur = p0.next;
        for (int i = 0; i < right - left + 1; ++i) {
            ListNode nxt = cur.next;
            cur.next = pre; // 每次循环只修改一个 next，方便大家理解
            pre = cur;
            cur = nxt;
        }

        // 见视频
        p0.next.next = cur;
        p0.next = pre;
        return dummy.next;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
